package ink.lovejinhu.swardToOffer;

import ink.lovejinhu.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

public class Offer_028 {
    /**
     * 对称二叉树
     * 左中右  右中左  应相同
     * 层序遍历不行，超内存
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);

        while (!treeNodes.isEmpty()) {
            if (treeNodes.size() == 1) {
                TreeNode poll = treeNodes.poll();
                treeNodes.add(poll.left);
                treeNodes.add(poll.right);
                continue;
            } else {
                ArrayList<Integer> integers = new ArrayList<>();
                boolean flag = false;
                for (int i = treeNodes.size(); i > 0; i--) {
                    TreeNode poll = treeNodes.poll();
                    if (poll == null) {
                        integers.add(Integer.MAX_VALUE);
                        treeNodes.add(null);  //左也是null
                        treeNodes.add(null);  //右也是null
                    } else {
                        flag = true;
                        integers.add(poll.val);
                        treeNodes.add(poll.left);
                        treeNodes.add(poll.right);
                    }

                }
                for (int i = 0, j = integers.size() - 1; i < j; i++, j--) {
                    if (!integers.get(i).equals(integers.get(j))) {
                        return false;
                    }
                }
                if (flag == false) {
                    break;
                }

            }
        }
        return true;

    }

    public boolean isSymmetric01(TreeNode root) {
        if (root == null) {
            return true;
        }

        return dfs(root.left, root.right);

    }

    public boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left != null && right != null) {
            if (left.val != right.val) {
                return false;
            }
            return dfs(left.left, right.right) && dfs(left.right, right.left);
        } else {
            return false;
        }

    }
}
